home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / bsp2poly.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  24KB  |  657 lines
  1. /******************************************************************************
  2. * Bsp2Poly.c - Bezier to polygon/polylines conversion routines.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. static CagdPolygonStruct *BspC1Srf2Polygons(CagdSrfStruct *Srf,
  10.                         int FineNess,
  11.                         CagdBType ComputeNormals,
  12.                         CagdBType FourPerFlat,
  13.                         CagdBType ComputeUV);
  14.  
  15. /*****************************************************************************
  16. * DESCRIPTION:                                                               M
  17. *   Routine to convert a single Bspline surface to set of triangles         M
  18. * approximating it. FineNess is a fineness control on result and the larger  M
  19. t is more triangles may result. A value of 10 is a good start value.         M
  20. * NULL is returned in case of an error, otherwise list of CagdPolygonStruct. M
  21. *   This routine looks for C1 discontinuities in the surface and splits it   M
  22. * into C1 continuous patches to invoke BspC1Srf2Polygons to gen. polygons.   M
  23. *                                                                            *
  24. * PARAMETERS:                                                                M
  25. *   Srf:              To approximate into triangles.                         M
  26. *   FineNess:         Control on accuracy, the higher the finer.             M
  27. *   ComputeNormals:   If TRUE, normal information is also computed.          M
  28. *   FourPerFlat:      If TRUE, four triangles are created per flat surface.  M
  29. *                     If FALSE, only 2 triangles are created.                M
  30. *   ComputeUV:        If TRUE, UV values are stored and returned as well.    M
  31. *                                                                            *
  32. * RETURN VALUE:                                                              M
  33. *   CagdPolygonStruct *:  A list of polygons with optional normal and/or     M
  34. *                         UV parametric information.                         M
  35. *                         NULL is returned in case of an error.              M
  36. *                                                                            *
  37. * KEYWORDS:                                                                  M
  38. *   BspSrf2Polygons, polygonization, surface approximation                   M
  39. *****************************************************************************/
  40. CagdPolygonStruct *BspSrf2Polygons(CagdSrfStruct *Srf,
  41.                    int FineNess,
  42.                    CagdBType ComputeNormals,
  43.                    CagdBType FourPerFlat,
  44.                    CagdBType ComputeUV)
  45. {
  46.     CagdBType HasUDiscont, HasVDiscont,
  47.     NewSrf = FALSE;
  48.     int ULength, VLength,
  49.     UOrder = Srf -> UOrder,
  50.     VOrder = Srf -> VOrder;
  51.     CagdRType u, v;
  52.     CagdPolygonStruct *Poly;
  53.  
  54.     if (CAGD_IS_PERIODIC_SRF(Srf)) {
  55.         NewSrf = TRUE;
  56.         Srf = CnvrtPeriodic2FloatSrf(Srf);
  57.     }
  58.  
  59.     ULength = Srf -> ULength;
  60.     VLength = Srf -> VLength;
  61.     HasUDiscont = BspKnotC1Discont(Srf -> UKnotVector, UOrder, ULength, &u);
  62.     HasVDiscont = BspKnotC1Discont(Srf -> VKnotVector, VOrder, VLength, &v);
  63.  
  64.     if (HasUDiscont || HasVDiscont) {
  65.     CagdSrfStruct
  66.         *Srf1 = HasUDiscont ? BspSrfSubdivAtParam(Srf, u,
  67.                               CAGD_CONST_U_DIR)
  68.                 : BspSrfSubdivAtParam(Srf, v,
  69.                               CAGD_CONST_V_DIR),
  70.         *Srf2 = Srf1 -> Pnext;
  71.     CagdPolygonStruct
  72.         *Poly1 = BspSrf2Polygons(Srf1, FineNess,
  73.                      ComputeNormals, FourPerFlat, ComputeUV),
  74.         *Poly2 = BspSrf2Polygons(Srf2, FineNess,
  75.                      ComputeNormals, FourPerFlat, ComputeUV);
  76.  
  77.     CagdSrfFreeList(Srf1);
  78.  
  79.     /* Chain the two lists together: */
  80.     if (Poly1 == NULL)
  81.         Poly = Poly2;
  82.     else if (Poly2 == NULL)
  83.         Poly = Poly1;
  84.     else {
  85.         for (Poly = Poly1; Poly -> Pnext != NULL; Poly = Poly -> Pnext);
  86.         Poly -> Pnext = Poly2;
  87.         Poly = Poly1;
  88.     }
  89.     }
  90.     else
  91.     Poly = BspC1Srf2Polygons(Srf, FineNess, ComputeNormals, FourPerFlat,
  92.                                  ComputeUV);
  93.  
  94.     if (NewSrf)
  95.     CagdSrfFree(Srf);
  96.  
  97.     return Poly;
  98. }
  99.  
  100. /*****************************************************************************
  101. * DESCRIPTION:                                                               *
  102. *   Routine to convert a single C1 continuouse Bspline srf to a set of       *
  103. * triangles approximating it. FineNess is a finess control on result and the *
  104. * larger it is more triangles may result. A value of 10 is a good starting   *
  105. * value. NULL is returned in case of an error, otherwise list of             *
  106. * CagdPolygonStruct.                                 *
  107. *                                                                            *
  108. * PARAMETERS:                                                                *
  109. *   Srf:              To approximate into triangles.                         *
  110. *   FineNess:         Control on accuracy, the higher the finer.             *
  111. *   ComputeNormals:   If TRUE, normal information is also computed.          *
  112. *   FourPerFlat:      If TRUE, four triangles are created per flat surface.  *
  113. *                     If FALSE, only 2 triangles are created.                *
  114. *   ComputeUV:        If TRUE, UV values are stored and returned as well.    *
  115. *                                                                            *
  116. * RETURN VALUE:                                                              *
  117. *   CagdPolygonStruct *:  A list of polygons with optional normal and/or     *
  118. *                         UV parametric information.                         *
  119. *                         NULL is returned in case of an error.              *
  120. *****************************************************************************/
  121. static CagdPolygonStruct *BspC1Srf2Polygons(CagdSrfStruct *Srf,
  122.                         int FineNess,
  123.                         CagdBType ComputeNormals,
  124.                         CagdBType FourPerFlat,
  125.                         CagdBType ComputeUV)
  126. {
  127.     int i, j, FineNessU1, FineNessV1, FineNessU, FineNessV, BaseIndex;
  128.     CagdRType u, v, UMin, UMax, VMin, VMax, *Pt;
  129.     CagdPointType
  130.     PType = Srf -> PType;
  131.     CagdPtStruct PtCenter, *Pt1, *Pt2, *Pt3, *Pt4, *PtMesh, *PtMeshPtr;
  132.     CagdUVStruct UVCenter,
  133.     *UVMeshPtr = NULL,
  134.     *UV1 = NULL,
  135.     *UV2 = NULL,
  136.     *UV3 = NULL,
  137.     *UV4 = NULL,
  138.     *UVMesh = NULL;
  139.     CagdVecStruct NlCenter,
  140.     *Nl1 = NULL,
  141.     *Nl2 = NULL,
  142.     *Nl3 = NULL,
  143.     *Nl4 = NULL,
  144.     *PtNrml = NULL;
  145.     CagdCrvStruct *Crv;
  146.     CagdPolygonStruct *Poly,
  147.     *PolyHead = NULL;
  148.  
  149.     if (!CAGD_IS_BSPLINE_SRF(Srf))
  150.     return NULL;
  151.  
  152.     /* Simple heuristic to estimate how many samples to compute. */
  153.     FineNessU = Srf -> ULength * FineNess / 10;
  154.     FineNessV = Srf -> VLength * FineNess / 10;
  155.  
  156.     if (FineNessU < 2)
  157.     FineNessU = 2;
  158.     if (FineNessV < 2)
  159.     FineNessV = 2;
  160.     switch (_CagdLin2Poly) {
  161.     case CAGD_REG_POLY_PER_LIN:
  162.         break;
  163.         case CAGD_ONE_POLY_PER_LIN:
  164.         if (Srf -> UOrder == 2)
  165.         FineNessU = 2;
  166.         if (Srf -> VOrder == 2)
  167.         FineNessV = 2;
  168.         break;
  169.         case CAGD_ONE_POLY_PER_COLIN:
  170.         break;
  171.     }
  172.     FineNessU1 = FineNessU - 1;
  173.     FineNessV1 = FineNessV - 1;
  174.  
  175.     /* Current to surface property such as curvature is used as subdivison   */
  176.     /* criterion and the surface is subdivided, equally spaced in parametric */
  177.     /* space, using FineNess as number of subdivisions per axis.         */
  178.  
  179.     /* Allocate a mesh to hold all vertices so common vertices need not be   */
  180.     /* Evaluated twice, and evaluate the surface at these mesh points.         */
  181.     PtMeshPtr = PtMesh = CagdPtArrayNew(FineNessU * FineNessV);
  182.  
  183.     if (ComputeUV)
  184.     UVMeshPtr = UVMesh = CagdUVArrayNew(FineNessU * FineNessV);
  185.  
  186.     BspSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  187.  
  188.     for (i = 0; i < FineNessU; i++) {
  189.     u = UMin + (UMax - UMin) * i / ((CagdRType) FineNessU1);
  190.     Crv = BspSrfCrvFromSrf(Srf, u, CAGD_CONST_U_DIR);
  191.  
  192.     for (j = 0; j < FineNessV; j++, PtMeshPtr++) {
  193.         v = VMin + (VMax - VMin) * j / ((CagdRType) FineNessV1);
  194.         Pt = BspCrvEvalAtParam(Crv, v);
  195.         CagdCoerceToE3(PtMeshPtr -> Pt, &Pt, -1, PType);
  196.  
  197.         if (ComputeUV) {
  198.         UVMeshPtr -> UV[0] = u;
  199.         UVMeshPtr -> UV[1] = v;
  200.         UVMeshPtr++;
  201.         }
  202.     }
  203.  
  204.     CagdCrvFree(Crv);
  205.     }
  206.  
  207.     if (ComputeNormals) {
  208.     if ((PtNrml = BspSrfMeshNormals(Srf, FineNessU, FineNessV)) == NULL)
  209.         ComputeNormals = FALSE;
  210.     }
  211.  
  212.     /* Now that we have the mesh, create the polygons. */
  213.     for (i = 0; i < FineNessU1; i++)
  214.     for (j = 0; j < FineNessV1; j++) {
  215.         BaseIndex = i * FineNessV + j;
  216.         Pt1 = &PtMesh[BaseIndex];        /* Cache the four flat corners. */
  217.         Pt2 = &PtMesh[BaseIndex + 1];
  218.         Pt3 = &PtMesh[BaseIndex + FineNessV + 1];
  219.         Pt4 = &PtMesh[BaseIndex + FineNessV];
  220.  
  221.         if (ComputeNormals) {
  222.         Nl1 = &PtNrml[BaseIndex];
  223.         Nl2 = &PtNrml[BaseIndex + 1];
  224.         Nl3 = &PtNrml[BaseIndex + FineNessV + 1];
  225.         Nl4 = &PtNrml[BaseIndex + FineNessV];
  226.         }
  227.  
  228.         if (ComputeUV) {
  229.         UV1 = &UVMesh[BaseIndex];
  230.         UV2 = &UVMesh[BaseIndex + 1];
  231.         UV3 = &UVMesh[BaseIndex + FineNessV + 1];
  232.         UV4 = &UVMesh[BaseIndex + FineNessV];
  233.         }
  234.  
  235.         if (FourPerFlat) {  /* Eval middle point and create 4 triangles. */
  236.         CAGD_COPY_POINT(PtCenter, *Pt1);
  237.         CAGD_ADD_POINT(PtCenter, *Pt2);
  238.         CAGD_ADD_POINT(PtCenter, *Pt3);
  239.         CAGD_ADD_POINT(PtCenter, *Pt4);
  240.         CAGD_MULT_POINT(PtCenter, 0.25);
  241.  
  242.         if (ComputeNormals) {
  243.             /* Average the four normals to find the middle one. */
  244.             CAGD_COPY_VECTOR(NlCenter, *Nl1);
  245.             CAGD_ADD_VECTOR(NlCenter, *Nl2);
  246.             CAGD_ADD_VECTOR(NlCenter, *Nl3);
  247.             CAGD_ADD_VECTOR(NlCenter, *Nl4);
  248.             CAGD_NORMALIZE_VECTOR(NlCenter);
  249.         }
  250.  
  251.         if (ComputeUV) {
  252.             UVCenter.UV[0] = (UV1 -> UV[0] + UV2 -> UV[0] +
  253.                       UV3 -> UV[0] + UV4 -> UV[0]) / 4.0;
  254.             UVCenter.UV[1] = (UV1 -> UV[1] + UV2 -> UV[1] +
  255.                       UV3 -> UV[1] + UV4 -> UV[1]) / 4.0;
  256.         }
  257.  
  258.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  259.                     Pt1, Pt2, &PtCenter,
  260.                     Nl1, Nl2, &NlCenter,
  261.                     UV1, UV2, &UVCenter);
  262.         if (Poly)
  263.             LIST_PUSH(Poly, PolyHead);
  264.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  265.                     Pt2, Pt3, &PtCenter,
  266.                     Nl2, Nl3, &NlCenter,
  267.                     UV2, UV3, &UVCenter);
  268.         if (Poly)
  269.             LIST_PUSH(Poly, PolyHead);
  270.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  271.                     Pt3, Pt4, &PtCenter,
  272.                     Nl3, Nl4, &NlCenter,
  273.                     UV3, UV4, &UVCenter);
  274.         if (Poly)
  275.             LIST_PUSH(Poly, PolyHead);
  276.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  277.                     Pt4, Pt1, &PtCenter,
  278.                     Nl4, Nl1, &NlCenter,
  279.                     UV4, UV1, &UVCenter);
  280.         if (Poly)
  281.             LIST_PUSH(Poly, PolyHead);
  282.         }
  283.         else {               /* Only two along the diagonal... */
  284.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  285.                     Pt1, Pt2, Pt3,
  286.                     Nl1, Nl2, Nl3,
  287.                     UV1, UV2, UV3);
  288.         if (Poly)
  289.             LIST_PUSH(Poly, PolyHead);
  290.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  291.                     Pt3, Pt4, Pt1,
  292.                     Nl3, Nl4, Nl1,
  293.                     UV3, UV4, UV1);
  294.         if (Poly)
  295.             LIST_PUSH(Poly, PolyHead);
  296.         }
  297.     }
  298.  
  299.     CagdPtArrayFree(PtMesh, FineNessU * FineNessV);
  300.     if (ComputeNormals)
  301.     CagdVecArrayFree(PtNrml, FineNessU * FineNessV);
  302.     if (ComputeUV)
  303.     CagdUVArrayFree(UVMesh, FineNessU * FineNessV);
  304.  
  305.     return PolyHead;
  306. }
  307.  
  308. /*****************************************************************************
  309. * DESCRIPTION:                                                               M
  310. *   Routine to convert a single Bspline surface to NumOfIsolines polylines   M
  311. * in each parametric direction with SamplesPerCurve in each isoparametric    M
  312. * curve.                                                                     M
  313. *   Polyline are always E3 of CagdPolylineStruct type.                 M
  314. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  315. *   NULL is returned in case of an error, otherwise list of                  M
  316. * CagdPolylineStruct. Attempt is made to extract isolines along C1           M
  317. * discontinuities first.                             M
  318. *                                                                            *
  319. * PARAMETERS:                                                                M
  320. *   Srf:                 Srf to extract isoparametric curves from.           M
  321. *   NumOfIsocurves:      To extarct from Srf in each (U or V) direction.     M
  322. *   SamplesPerCurve:     Fineness control on piecewise linear curve          M
  323. *                        approximation.                                      M
  324. *                                                                            *
  325. * RETURN VALUE:                                                              M
  326. *   CagdPolylineStruct *: List of polygons representing a piecewise linear   M
  327. *                         approximation of the extracted isoparamteric       M
  328. *                         curves or NULL is case of an error.                M
  329. *                                                                            *
  330. * KEYWORDS:                                                                  M
  331. *   BspSrf2Polylines, polylines, isoparametric curves                        M
  332. *****************************************************************************/
  333. CagdPolylineStruct *BspSrf2Polylines(CagdSrfStruct *Srf,
  334.                      int NumOfIsocurves[2],
  335.                      int SamplesPerCurve)
  336. {
  337.     CagdBType
  338.     NewSrf = FALSE;
  339.     int i, NumC1Disconts, NumOfIsos, ULength, VLength,
  340.     UOrder = Srf -> UOrder,
  341.     VOrder = Srf -> VOrder;
  342.     CagdRType u, v, UMin, UMax, VMin, VMax, *C1Disconts, *IsoParams, *RefKV,
  343.     *UKV, *VKV;
  344.     CagdCrvStruct *Crv;
  345.     CagdPolylineStruct *Poly,
  346.     *PolyList = NULL;
  347.     BspKnotAlphaCoeffType *A;
  348.  
  349.     if (!CAGD_IS_BSPLINE_SRF(Srf))
  350.     return NULL;
  351.  
  352.     if (CAGD_IS_PERIODIC_SRF(Srf)) {
  353.         NewSrf = TRUE;
  354.         Srf = CnvrtPeriodic2FloatSrf(Srf);
  355.     }
  356.  
  357.     UKV = Srf -> UKnotVector;
  358.     VKV = Srf -> VKnotVector;
  359.     ULength = Srf -> ULength;
  360.     VLength = Srf -> VLength;
  361.  
  362.     /* Make sure the curve is open. We move 2 Epsilons to make sure region  */
  363.     /* extraction will occur. Otherwise the curve will be copied as is.     */
  364.     if (!BspKnotHasOpenEC(UKV, ULength, UOrder) ||
  365.     !BspKnotHasOpenEC(VKV, VLength, VOrder)) {
  366.     CagdSrfStruct
  367.         *TSrf = CagdSrfRegionFromSrf(Srf,
  368.                      UKV[UOrder - 1],
  369.                      UKV[ULength],
  370.                      CAGD_CONST_U_DIR);
  371.  
  372.     if (NewSrf)
  373.         CagdSrfFree(Srf);
  374.  
  375.     Srf = CagdSrfRegionFromSrf(TSrf,
  376.                    VKV[VOrder - 1],
  377.                    VKV[VLength],
  378.                    CAGD_CONST_V_DIR);
  379.     NewSrf = TRUE;
  380.  
  381.     CagdSrfFree(TSrf);
  382.     }
  383.  
  384.     /* Make sure requested format is something reasonable. */
  385.     if (SamplesPerCurve < 2)
  386.     SamplesPerCurve = 2;
  387.     if (NumOfIsocurves[0] < 2)
  388.     NumOfIsocurves[0] = 2;
  389.     if (NumOfIsocurves[1] <= 0)
  390.     NumOfIsocurves[1] = NumOfIsocurves[0];
  391.     else if (NumOfIsocurves[1] < 2)
  392.     NumOfIsocurves[1] = 2;
  393.  
  394.     BspSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  395.  
  396.     /* Compute discontinuities along the u axis and use that to determine    */
  397.     /* where to extract isolines along u.                     */
  398.     /* Note C1Disconts is freed by BspKnotParamValues.                 */
  399.  
  400.     /* Add heuristically more samples if surface has interior knots.         */
  401.     NumOfIsos = NumOfIsocurves[0];
  402.     if (UOrder > 2)
  403.     NumOfIsos += (ULength - UOrder) / 2;
  404.  
  405.     C1Disconts = BspKnotAllC1Discont(Srf -> UKnotVector, UOrder,
  406.                      ULength, &NumC1Disconts);
  407.     IsoParams = BspKnotParamValues(UMin, UMax, NumOfIsos, C1Disconts,
  408.                                 NumC1Disconts);
  409.     RefKV = BspKnotPrepEquallySpaced(MAX(SamplesPerCurve - VLength, 1),
  410.                      VMin, VMax);
  411.     A = BspKnotEvalAlphaCoefMerge(VOrder, Srf -> VKnotVector, VLength, RefKV,
  412.                   MAX(SamplesPerCurve - VLength, 1));
  413.     IritFree((VoidPtr) RefKV);
  414.  
  415.     for (i = 0; i < NumOfIsos; i++) {
  416.     u = IsoParams[i];
  417.  
  418.     Crv = BspSrfCrvFromSrf(Srf, u, CAGD_CONST_U_DIR);
  419.     Poly = BspCrv2Polyline(Crv, SamplesPerCurve, A, TRUE);
  420.     Poly -> Pnext = PolyList;
  421.     PolyList = Poly;
  422.     CagdCrvFree(Crv);
  423.     }
  424.     IritFree((VoidPtr) IsoParams);
  425.     BspKnotFreeAlphaCoef(A);
  426.  
  427.     /* Compute discontinuities along the v axis and use that to determine    */
  428.     /* where to extract isolines along v.                     */
  429.     /* Note C1Disconts is freed by BspKnotParamValues.                 */
  430.  
  431.     /* Add heuristically more samples if surface has interior knots.         */
  432.     NumOfIsos = NumOfIsocurves[1];
  433.     if (VOrder > 2)
  434.     NumOfIsos += (VLength - VOrder) / 2;
  435.  
  436.     C1Disconts = BspKnotAllC1Discont(Srf -> VKnotVector, VOrder,
  437.                      VLength, &NumC1Disconts);
  438.     IsoParams = BspKnotParamValues(VMin, VMax, NumOfIsos, C1Disconts,
  439.                                 NumC1Disconts);
  440.     RefKV = BspKnotPrepEquallySpaced(MAX(SamplesPerCurve - ULength, 1),
  441.                      UMin, UMax);
  442.     A = BspKnotEvalAlphaCoefMerge(UOrder, Srf -> UKnotVector, ULength, RefKV,
  443.                   MAX(SamplesPerCurve - ULength, 1));
  444.     IritFree((VoidPtr) RefKV);
  445.  
  446.     for (i = 0; i < NumOfIsos; i++) {
  447.     v = IsoParams[i];
  448.  
  449.     Crv = BspSrfCrvFromSrf(Srf, v, CAGD_CONST_V_DIR);
  450.     Poly = BspCrv2Polyline(Crv, SamplesPerCurve, A, TRUE);
  451.     Poly -> Pnext = PolyList;
  452.     PolyList = Poly;
  453.     CagdCrvFree(Crv);
  454.     }
  455.     IritFree((VoidPtr) IsoParams);
  456.     BspKnotFreeAlphaCoef(A);
  457.  
  458.     if (NewSrf)
  459.     CagdSrfFree(Srf);
  460.  
  461.     return PolyList;
  462. }
  463.  
  464. /*****************************************************************************
  465. * DESCRIPTION:                                                               M
  466. *   Routine to extract from a Bspline surface NumOfIsoline isocurve list     M
  467. * in each param. direction.                             M
  468. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  469. *   NULL is returned in case of an error, otherwise list of CagdCrvStruct.   M
  470. *                                                                            *
  471. * PARAMETERS:                                                                M
  472. *   Srf:             To extract isoparametric curves from.                   M
  473. *   NumOfIsocurves:  In each (U or V) direction.                             M
  474. *                                                                            *
  475. * RETURN VALUE:                                                              M
  476. *   CagdCrvStruct *:  List of extracted isoparametric curves. These curves   M
  477. *                     inherit the order and continuity of the original Srf.  M
  478. *                     NULL is returned in case of an error.                  M
  479. *                                                                            *
  480. * KEYWORDS:                                                                  M
  481. *   BspSrf2Curves, curves, isoparametric curves                              M
  482. *****************************************************************************/
  483. CagdCrvStruct *BspSrf2Curves(CagdSrfStruct *Srf, int NumOfIsocurves[2])
  484. {
  485.     int i, NumC1Disconts,
  486.     ULength = Srf -> ULength,
  487.     VLength = Srf -> VLength,
  488.     UOrder = Srf -> UOrder,
  489.     VOrder = Srf -> VOrder;
  490.     CagdRType u, v, UMin, UMax, VMin, VMax, *C1Disconts, *IsoParams;
  491.     CagdCrvStruct *Crv,
  492.     *CrvList = NULL;
  493.  
  494.     if (!CAGD_IS_BSPLINE_SRF(Srf))
  495.     return NULL;
  496.  
  497.     /* Make sure requested format is something reasonable. */
  498.     if (NumOfIsocurves[0] < 2)
  499.     NumOfIsocurves[0] = 2;
  500.     if (NumOfIsocurves[1] <= 0)
  501.     NumOfIsocurves[1] = NumOfIsocurves[0];
  502.     else if (NumOfIsocurves[1] < 2)
  503.     NumOfIsocurves[1] = 2;
  504.  
  505.     BspSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  506.  
  507.     /* Compute discontinuities along the u axis and use that to determine    */
  508.     /* where to extract isolines along u.                     */
  509.     /* Note C1Disconts is freed by BspKnotParamValues.                 */
  510.     C1Disconts = BspKnotAllC1Discont(Srf -> UKnotVector, UOrder,
  511.                      ULength, &NumC1Disconts);
  512.     IsoParams = BspKnotParamValues(UMin, UMax, NumOfIsocurves[0], C1Disconts,
  513.                                 NumC1Disconts);
  514.  
  515.     for (i = 0; i < NumOfIsocurves[0]; i++) {
  516.     u = IsoParams[i];
  517.  
  518.     Crv = BspSrfCrvFromSrf(Srf, u, CAGD_CONST_U_DIR);
  519.     Crv -> Pnext = CrvList;
  520.     CrvList = Crv;
  521.     }
  522.     IritFree((VoidPtr) IsoParams);
  523.  
  524.     /* Compute discontinuities along the v axis and use that to determine    */
  525.     /* where to extract isolines along v.                     */
  526.     /* Note C1Disconts is freed by BspKnotParamValues.                 */
  527.     C1Disconts = BspKnotAllC1Discont(Srf -> VKnotVector, VOrder,
  528.                      VLength, &NumC1Disconts);
  529.     IsoParams = BspKnotParamValues(VMin, VMax, NumOfIsocurves[1], C1Disconts,
  530.                                 NumC1Disconts);
  531.  
  532.     for (i = 0; i < NumOfIsocurves[1]; i++) {
  533.     v = IsoParams[i];
  534.  
  535.     Crv = BspSrfCrvFromSrf(Srf, v, CAGD_CONST_V_DIR);
  536.     Crv -> Pnext = CrvList;
  537.     CrvList = Crv;
  538.     }
  539.     IritFree((VoidPtr) IsoParams);
  540.  
  541.     return CrvList;
  542. }
  543.  
  544. /*****************************************************************************
  545. * DESCRIPTION:                                                               M
  546. *   Routine to approx. a single Bspline curve as a polyline with         M
  547. * SamplesPerCurve samples. Polyline is always E3 CagdPolylineStruct type.    M
  548. *   Curve is refined equally spaced in parametric space, unless the curve is M
  549. * linear in which the control polygon is simply being copied.             M
  550. *   If A is specified, it is used to refine the curve.                 M
  551. *   NULL is returned in case of an error, otherwise CagdPolylineStruct.         M
  552. *                                                                            *
  553. * PARAMETERS:                                                                M
  554. *   Crv:              To approximate as a polyline.                          M
  555. *   SamplesPerCurve:  Number of samples to approximate with.                 M
  556. *   A:                Alpha matrix (Oslo algorithm) if precumputed.          M
  557. *   OptiLin:          If TRUE, optimize linear curves.                 M
  558. *                                                                            *
  559. * RETURN VALUE:                                                              M
  560. *   CagdPolylineStruct *:  A polyline representing the piecewise linear      M
  561. *                          approximation from, or NULL in case of an error.  M
  562. *                                                                            *
  563. * KEYWORDS:                                                                  M
  564. *   BspCrv2Polyline, piecewise linear approximation, polyline                M
  565. *****************************************************************************/
  566. CagdPolylineStruct *BspCrv2Polyline(CagdCrvStruct *Crv,
  567.                     int SamplesPerCurve,
  568.                     BspKnotAlphaCoeffType *A,
  569.                     CagdBType OptiLin)
  570. {
  571.     CagdBType
  572.     NewCrv = FALSE;
  573.     int i, j, n,
  574.     Order = Crv -> Order,
  575.     Len = Crv -> Length,
  576.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv),
  577.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  578.     CagdRType *Polyline[CAGD_MAX_PT_SIZE],
  579.     *KV = Crv -> KnotVector;
  580.     CagdPolylnStruct *NewPolyline;
  581.     CagdPolylineStruct *P;
  582.  
  583.     if (!CAGD_IS_BSPLINE_CRV(Crv))
  584.     return NULL;
  585.  
  586.     if (CAGD_IS_PERIODIC_CRV(Crv)) {
  587.         Crv = CnvrtPeriodic2FloatCrv(Crv);
  588.     Len += Order - 1;
  589.     KV = Crv -> KnotVector;
  590.     NewCrv = TRUE;
  591.     }
  592.  
  593.     /* Make sure the curve is open. We move 2 Epsilons to make sure region  */
  594.     /* extraction will occur. Otherwise the curve will be copied as is.     */
  595.     if (!BspKnotHasOpenEC(KV, Len, Order)) {
  596.     CagdCrvStruct
  597.         *TCrv = CagdCrvRegionFromCrv(Crv, KV[Order - 1], KV[Len]);
  598.  
  599.     if (NewCrv)
  600.         CagdCrvFree(Crv);
  601.     Crv = TCrv;
  602.     NewCrv = TRUE;
  603.     }
  604.  
  605.     /* Make sure requested format is something reasonable. */
  606.     if (SamplesPerCurve < 2)
  607.     SamplesPerCurve = 2;
  608.  
  609.     if (SamplesPerCurve <= Len || (Order == 2 && OptiLin)) {
  610.     /* Make sure SamplesPerCurve can hold the entire control polygon. */
  611.     SamplesPerCurve = Len + 1;
  612.     }
  613.  
  614.     n = MAX(A ? A -> RefLength : 0, SamplesPerCurve);
  615.  
  616.     P = CagdPolylineNew(n);
  617.     NewPolyline = P -> Polyline;
  618.  
  619.     /* Allocate temporary memory to hold evaluated curve. */
  620.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++)
  621.     Polyline[i] = (CagdRType *) IritMalloc(sizeof(CagdRType) * n);
  622.  
  623.     if (MaxCoord > 3)
  624.     MaxCoord = 3;
  625.  
  626.     n = P -> Length = CagdCrvEvalToPolyline(Crv,
  627.                         A == NULL ? n : 0,
  628.                         Polyline, A, OptiLin);
  629.     if (IsNotRational){
  630.     for (i = n - 1; i >= 0; i--) {              /* Convert to E3 polyline. */
  631.         for (j = 0; j < MaxCoord; j++)
  632.         NewPolyline[i].Pt[j] = Polyline[j + 1][i];
  633.         for (j = MaxCoord; j < 3; j++)
  634.         NewPolyline[i].Pt[j] = 0.0;
  635.     }
  636.     }
  637.     else {
  638.     for (i = n - 1; i >= 0; i--) {              /* Convert to E3 polyline. */
  639.         CagdRType
  640.         PtW = Polyline[0][i] == 0 ? IRIT_EPSILON : Polyline[0][i];
  641.  
  642.         for (j = 0; j < MaxCoord; j++)
  643.         NewPolyline[i].Pt[j] = Polyline[j + 1][i] / PtW;
  644.         for (j = MaxCoord; j < 3; j++)
  645.         NewPolyline[i].Pt[j] = 0.0;
  646.     }
  647.     }
  648.  
  649.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++)
  650.     IritFree((VoidPtr) Polyline[i]);
  651.  
  652.     if (NewCrv)
  653.     CagdCrvFree(Crv);
  654.  
  655.     return P;
  656. }
  657.